package OptimalAlgorithm.Linkedlist;

import java.util.PriorityQueue;

//https://leetcode.cn/problems/merge-k-sorted-lists/description/
public class MergeKLists {
    //方法一：利用优先级队列进行排序合并
/*    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null){
            return null;
        }
        int k = lists.length;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);//传入一个比较器（lambda表达式）
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        for (int i = 0; i < k; i++) {
            if(lists[i] != null){
                priorityQueue.offer(lists[i]);
            }
        }
        while (!priorityQueue.isEmpty()){
            ListNode top = priorityQueue.poll();
            cur.next = top;
            cur = cur.next;
            top = top.next;
            if(top != null){
                priorityQueue.offer(top);
            }
        }
        return newHead.next;
    }*/

    //方法二：利用分治-递归的方法合并链表
    public ListNode mergeKLists(ListNode[] lists) {
        int left = 0;
        int  right = lists.length - 1;
        return merge(lists,left,right);
    }
    private ListNode merge(ListNode[] lists,int left,int right){
        if(left > right){
            return null;
        }
        if(left == right){
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode L1 = merge(lists,left,mid);
        ListNode L2 = merge(lists,mid + 1 ,right);
        return mergeList(L1,L2);
    }
    //合并两个有序链表
    private ListNode mergeList(ListNode l1,ListNode l2){
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while (cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur.next = cur1;
                cur = cur.next;
                cur1 = cur1.next;
            }else {
                cur.next = cur2;
                cur = cur.next;
                cur2 = cur2.next;
            }
        }
        while (cur1 != null){
            cur.next = cur1;
            cur = cur.next;
            cur1 = cur1.next;
        }
        while (cur2 != null){
            cur.next = cur2;
            cur = cur.next;
            cur2 = cur2.next;
        }
        return newHead.next;
    }
}
